//
//  Problem1588.swift
//  TestProject
//
//  Created by 武侠 on 2021/4/9.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1588. 所有奇数长度子数组的和
 给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

 子数组 定义为原数组中的一个连续子序列。
 请你返回 arr 中 所有奇数长度子数组的和 。

 示例 1：
     输入：arr = [1,4,2,5,3]
     输出：58
     解释：所有奇数长度子数组和它们的和为：
     [1] = 1
     [4] = 4
     [2] = 2
     [5] = 5
     [3] = 3
     [1,4,2] = 7
     [4,2,5] = 11
     [2,5,3] = 10
     [1,4,2,5,3] = 15
    我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
 示例 2：
     输入：arr = [1,2]
     输出：3
     解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
 示例 3：
     输入：arr = [10,11,12]
     输出：66
 提示：
     1 <= arr.length <= 100
     1 <= arr[i] <= 1000
 */
@objcMembers class Problem1588: NSObject {
    func solution() {
        print(sumOddLengthSubarrays([1,4,2,5,3]))
        print(sumOddLengthSubarrays([1,2]))
        print(sumOddLengthSubarrays([10,11,12]))
    }
    /*
     暴力破解
     1: 依次计算奇数个数的数组的和
     */
    func sumOddLengthSubarraysBao(_ arr: [Int]) -> Int {
        var result = 0
        var n = 1
        while n <= arr.count {
            var start = 0
            for end in n...arr.count {
                for i in start..<end {
                    result += arr[i]
                }
                start += 1
            }
            
            n += 2
        }
        return result
    }
    
    /*
     优化暴力破解，前缀和
     在最底层循环中，就是求[start, end]和，那么首先求前缀后
     1: 首先求出所有的前缀和
     */
    func sumOddLengthSubarraysBaoQian(_ arr: [Int]) -> Int {
        // 求前缀和
        var presum:[Int] = [0]
        for i in 1...arr.count {
            presum.append(presum[i-1] + arr[i-1])
        }
        
        var result = 0
        var n = 1
        while n <= arr.count {
            var start = 0
            for end in n...arr.count {
                result += presum[end] - presum[start]
                start += 1
            }
            
            n += 2
        }
        
        return result
    }
    /*
     查找每个元素，在几个数组中存在过，例如： [1, 4, 2, 5, 3] 中
     1 在 3 个长度为奇数的数组中出现过：[1], [1, 4, 2], [1, 4, 2, 5, 3]；所以最终的和，要加上 1 * 3；
     如何计算一个数字在多少个奇数长度的数组中出现过？
     以这个点为中心，左边的个数+右边的个数 = 偶数即可：左边奇数+右边奇数 或者 左边偶数+右边偶数
     例如求 arr[2] = 2, 以i=3为中心点:
     左边的奇数:[4]  i+1 / 2
     右边奇数:[5]   (count-i+1) / 2
     左边的偶数:[1,4] i / 2
     右边奇数:[5,3] (count-i) / 2
     
     
     */
    func sumOddLengthSubarrays(_ arr: [Int]) -> Int {
        var result = 0
        var left = 1
        var right = 1
        for i in 0..<arr.count {
            left = i + 1
            right = arr.count - i
            let left_ji = (left + 1) / 2
            let right_ji = (right + 1) / 2
            let left_ou = left / 2
            let right_ou = right / 2
            
            result += (left_ji * right_ji + left_ou * right_ou) * arr[i]
        }
        
        return result
    }
}
